Search Results

1. E. Hyytiä, A. Penttinen and R. Sulonen, Non-Myopic Vehicle and Route Selection in Dynamic DARP with Travel Time and Workload Objectives, Computers & Operations Research, vol. 39, no. 12, Elsevier, 2012 (link)(bib)

   Abstract: In dial-a-ride problems a fleet of n vehicles is routed to transport people between pick-up and delivery locations. We consider an elementary dynamic version of the problem where trip requests arrive in time and require an immediate vehicle assignment (which triggers an appropriate route plan update of the selected vehicle). In this context, a relatively general objective can be stated as a weighted sum of the system's effort and the customers' inconvenience. However, optimizing almost any objective in the resulting, immensely complex, stochastic system is prohibitively difficult and thus the earlier work has resorted to heuristic cost functions for vehicle routing and selection that arise, e.g., from the corresponding static systems. In this paper, by using the framework of Markov decision processes and the classical M/M/1 queue as a highly abstract model for a single vehicle, we explain why certain cost functions indeed give satisfactory results in the dynamic system, and also give an explicit interpretation of different components appearing in a general cost function. The resulting family of heuristic control policies is demonstrated to offer a desired type of performance thus justifying the assumed analogy between a group of M/M/1 queues and the dynamic dial-a-ride system.